package comprehensive;

public class Exercises13 {
    // 79、单词搜索
    boolean[][] cheack;
    int m;
    int n;
    char[] words;

    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        words = word.toCharArray();
        cheack = new boolean[m][n];

        // 找到和word单词的第一个相同的位置开始递归，进行上下左右进行查询遍历
        for(int i = 0;i < m;i++) {
            for(int j = 0;j < n;j++) {
                if(board[i][j] == words[0]) {
                    cheack[i][j] = true;
                    // words的0下标位置的值已经判断结束，我们从1下标开始判断
                    if(dfs(board,i,j,1) == true) {
                        return true;
                    }
                    cheack[i][j] = false;
                }
            }
        }
        return false;
    }

    // 这两个数组就是对于某个确定的位置的值，进行邻值的上下左右进行判断
    int[] dx = {1,-1,0,0};
    int[] dy = {0,0,1,-1};

    public boolean dfs(char[][] board,int i,int j,int pos) {
        if(pos == words.length) {
            return true;
        }

        // 利用dx和dy两个数组进行 上下左右的邻值进行判断
        for(int k = 0;k < 4;k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !cheack[x][y] && board[x][y] == words[pos]) {
                // 进入这里说明这个x，y位置的值是我们需要的值
                cheack[x][y] = true;
                if(dfs(board,x,y,pos + 1) == true) {
                    return true;
                }
                cheack[x][y] = false;
            }
        }
        // i，j位置的 上下左右 没有匹配上，进行返回false
        return false;
    }
}
